/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。

    思路：
    用栈
    1：遍历字符串  有左括号入栈  遇到和栈顶类型匹配的右括号出栈  类型不匹配直接false
    2：最后栈空了就true  没空就false

 */

/**
 * @param {string} s
 * @return {boolean}
 * 执行用时：68 ms, 在所有 JavaScript 提交中击败了78.71% 的用户
内存消耗：41.7 MB, 在所有 JavaScript 提交中击败了12.48% 的用户
通过测试用例：91 / 91
 */
var isValid = function (s) {
  let stack = [];
  // 遍历字符串
  for (let i = 0; i < s.length; i++) {
    // 有左括号入栈
    if (s[i] == "(" || s[i] == "[" || s[i] == "{") {
      stack.push(s[i]);
      // 遇到和栈顶类型匹配的右括号出栈
    }else if(s[i] == ")"){
      if((stack[stack.length - 1] == '(')){
        stack.pop()
      }else{
        // 类型不匹配直接false
        return false
      }
    }else if(s[i] == "]"){
      if((stack[stack.length - 1] == '[')){
        stack.pop()
      }else{
        return false
      }
    }else if(s[i] == "}"){
      if((stack[stack.length - 1] == '{')){
        stack.pop()
      }else{
        return false
      }
    }
  }
  return stack.length == 0 ? true : false

};


// 优化  如果是奇数  直接false
// map

var isValid = function(s) {
  const n = s.length;
  if (n % 2 === 1) {
      return false;
  }
  const pairs = new Map([
      [')', '('],
      [']', '['],
      ['}', '{']
  ]);
  const stk = [];
  for (let ch of s){
      if (pairs.has(ch)) {
          if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) {
              return false;
          }
          stk.pop();
      } 
      else {
          stk.push(ch);
      }
  };
  return !stk.length;
};



